/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/burst-balloons
   @Language: C++
   @Datetime: 19-04-12 14:42
   */


class Solution {
public:
	/**
	 * @param nums: A list of integer
	 * @return: An integer, maximum coins
	 * Tip:
	 * dp[i][j] as max coins when burst range [i,j],
	 * select k(i<k<j) as last bursted in range [i,j],
	 * when select k, dp[i][j]=dp[i][k-1]+dp[k+1][j]
	 *				+nums[i-1]*nums[k]*nums[j+1]
	 */
	int maxCoins(vector<int> &nums) {
		// write your code here
		int n=nums.size();
		nums.insert(nums.begin(),1);
		nums.push_back(1);
		vector<vector<int> > dp(n+2,vector<int>(n+2,0));
		for(int len=1; len<=n; ++len){
			for(int i=1; i+len<=n+1; ++i){
				for(int k=i, j=i+len-1; k<=j; ++k)
					dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k+1][j]+nums[i-1]*nums[k]*nums[j+1]);
			}
		}
		return dp[1][n];
	}
};
